'''
环形链表：
便利链表，每个节点和后面一个节点判断，如果后面连接到第一个节点，则有环。
'''

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False

    slow = head
    fast = head.next

    while slow != fast:
        # 链表为空
        if not fast or not fast.next:
            return False
        
        # 便利到下一个链表
        slow = slow.next
        fast = fast.next.next

    # slow == fast，cycled

    return True

# 辅助函数：创建带有环的链表
def createLinkedListWithCycle(values, pos):
    if not values:
        return None
    nodes = [ListNode(val) for val in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos != -1:
        nodes[-1].next = nodes[pos]
    return nodes[0]

# 测试用例
def test_hasCycle():
    # 测试用例 1
    head1 = createLinkedListWithCycle([3, 2, 0, -4], 1)
    print(f"Test case 1: {hasCycle(head1)}")  # 预期输出: True

    # 测试用例 2
    head2 = createLinkedListWithCycle([1, 2], 0)
    print(f"Test case 2: {hasCycle(head2)}")  # 预期输出: True

    # 测试用例 3
    head3 = createLinkedListWithCycle([1], -1)
    print(f"Test case 3: {hasCycle(head3)}")  # 预期输出: False

    # 测试用例 4
    head4 = createLinkedListWithCycle([], -1)
    print(f"Test case 4: {hasCycle(head4)}")  # 预期输出: False

    # 测试用例 5
    head5 = createLinkedListWithCycle([1, 2, 3, 4, 5], 2)
    print(f"Test case 5: {hasCycle(head5)}")  # 预期输出: True

# 运行测试用例
test_hasCycle()